/*
 * 1608. Two Sum II - Input array is sorted
 * 给定一个已经 按升序排列 的数组，找到两个数使他们加起来的和等于特定数。
 * 函数应该返回这两个数的下标，index1必须小于index2。注意返回的值不是 0-based。
 * 
 * 样例
 * 给定数组为 [2,7,11,15] ，target = 9
 * 返回 [1,2]
 * 
 * 2018.06.12 @jeyming
 */
package two_sum_ii_input_array_is_sorted_1608;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Two_sum_ii_input_array_is_sorted_1609 {
    /**
     * @param nums: an array of Integer
     * @param target: target = nums[index1] + nums[index2]
     * @return: [index1 + 1, index2 + 1] (index1 < index2)
     */
    public static int[] twoSum(int[] nums, int target) {
        // write your code here
    	List<Integer> list = new ArrayList<Integer>();
    	int cnt = 0;
    	for(int i = 0; i < nums.length; ++i) {
    		for(int j = i + 1; j < nums.length; ++j) {
    			if(nums[i] + nums[j] == target) {
    				if(list.contains(i + 1) == true && list.contains(j + 1) == true) {
    					break;
    				}
    				list.add(i + 1);
    				list.add(j + 1);
    				cnt += 2;
    				break;
    			}
    		}
    	}
    	int[] ans = new int[cnt];
    	for(int i = 0; i < cnt; ++i) {
    		ans[i] = list.get(i);
    	}
    	Arrays.sort(ans,0,cnt);
    	return ans;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int num[] = {2,7,11,15};
		int ans[] = twoSum(num,9);
		for(int i = 0; i < ans.length; ++i) {
			System.out.println(ans[i]);
		}
	}

}
